package com.aug_leo.datastructure.stack;

/**
 * 有效的括号
 * 需要满足
 * <ol>
 *     <li>左括号必须用相同类型的右括号闭合</li>
 *     <li>左括号必须以正确的顺序闭合</li>
 *     <li>每个右括号都有一个对应的相同类型的左括号</li>
 * </ol>
 */
public class E01Leetcode20 {
    public boolean isValid(String s) {
        // 根据字符串长度创建一个字符栈，用于存储匹配的右括号
        ArrayStack<Character> stack = new ArrayStack<>(s.length());

        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            // 如果是左圆括号，则将其对应的右圆括号压入栈中
            if (c == '(') {
                stack.push(')');
                // 如果是左方括号，则将其对应的右方括号压入栈中
            } else if (c == '[') {
                stack.push(']');
                // 如果是左花括号，则将其对应的右花括号压入栈中
            } else if (c == '{') {
                stack.push('}');
                // 如果是右括号
            } else {
                // 如果栈不为空且栈顶元素与当前右括号匹配，则弹出栈顶元素
                if (!stack.isEmpty() && c == stack.peek()) {
                    stack.pop();
                } else {
                    // 如果栈为空或栈顶元素与当前右括号不匹配，说明括号无效，返回false
                    return false;
                }
            }
        }
        // 如果栈为空，说明所有左括号都有匹配的右括号，返回true；否则，返回false
        return stack.isEmpty();
    }

    /*
        (   [   ]

        底 - 栈 - 顶
        )   ]

        遇到左括号, 把要配对的右括号放入栈顶
        遇到右括号, 把它与栈顶元素对比
            若相等, 栈顶元素弹出, 继续对比下一组
            若不等, 无效括号直接返回 false
     */

    public static void main(String[] args) {
        E01Leetcode20 s = new E01Leetcode20();
        System.out.println(s.isValid("([{}])"));
        System.out.println(s.isValid("()[]{}"));
        System.out.println(s.isValid("()"));
        System.out.println("---------------------");

        System.out.println(s.isValid("[)"));
        // ]
        System.out.println(s.isValid("([)]"));
        // ) ]
        System.out.println(s.isValid("([]"));
        // )
        System.out.println(s.isValid("("));

        System.out.println("---------------------");
        System.out.println(s.isValid(")("));
        System.out.println(s.isValid("]"));
    }
}
